package 第五周;

/*
 * @author  YxinMiracle
 * @date  2022-05-04 9:30
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 快数排序 {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
        return nums;
    }

    public void quickSort(int[] arr,int i,int j){
        if (i<j){
            int pivot = qsort(arr,i,j);
            quickSort(arr,i,pivot);
            quickSort(arr,pivot+1,j);
        }
    }

    public int qsort(int[] arr,int i,int j){
        int pivot = i + (int) (Math.random() * (j-i+1));
        int pivotVal = arr[pivot]; // 选取一个中值

        while (i <= j){
            while (arr[i] < pivotVal) i++;
            while (arr[j] > pivotVal) j--;
            if (i == j) break;
            if (i < j){
                int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
                i++;j--;
            }
        }
        return j;
    }

    public static void main(String[] args) {
        new 快数排序().sortArray(new int[]{5,2,3,1,4,6,4,4,2,3,4,44,5,-1,-3,-56,67,8});
    }

}
